﻿//986. 区间列表的交集
//给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 
//而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
//返回这 两个区间列表的交集 。
//形式上，闭区间[a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
//两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和[2, 4] 的交集为[2, 3] 。



class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList)
    {
        int i = 0, j = 0;
        int n = firstList.size(), m = secondList.size();
        vector<vector<int>> ans;
        while (i < n && j < m)
        {
            //不相交
            if (firstList[i][1] < secondList[j][0] || firstList[i][0] > secondList[j][1])
            {
                if (firstList[i][1] < secondList[j][0])      i++;
                else    j++;
            }
            else
            {
                int left = max(secondList[j][0], firstList[i][0]);
                int right = min(secondList[j][1], firstList[i][1]);
                ans.push_back({ left,right });
                if (secondList[j][1] > firstList[i][1])
                {
                    i++;
                }
                else
                {
                    j++;
                }
            }
        }
        return ans;
    }
};